#include <bits/stdc++.h>
using namespace std;
// #define int long long
long long ans=0;
int n,k,a[100005];
struct node{
    int l,r;
    int tag[4],sum[16];
}v[400005];
void push_up(int rt){
    if(v[rt].l==v[rt].r){
        memset(v[rt].sum,0,sizeof(v[rt].sum));
        v[rt].sum[0]=1;
    }else for(int i=0;i<(1<<k);i++)v[rt].sum[i]=(v[rt<<1].sum[i]+v[rt<<1|1].sum[i]);
    int T=0;
    for(int i=0;i<k;i++)T+=(1<<i)*(v[rt].tag[i]!=0);
    for(int i=0;i<(1<<k);i++){
        int nans=v[rt].sum[i];
        v[rt].sum[i]=0;
        v[rt].sum[i|T]+=nans;
    }
}
void push_tag(int rt,int id,int val){
    // if(v[rt].l==v[rt].r){
        // memset(v[rt].sum,0,sizeof(v[rt].sum));
        // v[rt].sum[0]=1;
    // }else push_up(rt);
    // int T=0;
    v[rt].tag[id]+=val;
    push_up(rt);
    
}
void build(int rt,int l,int r){
    v[rt].l=l;v[rt].r=r;
    for(int i=0;i<k;i++)v[rt].tag[i]=0;
    if(l==r){v[rt].sum[0]=1;return ;}
    int mid=(l+r)>>1;
    build(rt<<1,l,mid);build(rt<<1|1,mid+1,r);
    push_up(rt);
}
void add(int rt,int l,int r,int id,int val){
    if(l<=v[rt].l&&v[rt].r<=r){
        push_tag(rt,id,val);
        return;
    }
    int mid=(v[rt].l+v[rt].r)>>1;
    if(l<=mid)add(rt<<1,l,r,id,val);
    if(r>=mid+1)add(rt<<1|1,l,r,id,val);
    push_up(rt);
}
vector<int>vec[100005];
signed main() {
    freopen("reporter.in","r",stdin);
    freopen("reporter.out","w",stdout);
    ios::sync_with_stdio(0);
    cin.tie(0),cout.tie(0);
    cin>>n>>k;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        vec[i].push_back(0);
        // vec[a[i]].push_back(i);
    }
    build(1,1,n);
    for(int i=1;i<=n;i++){
        // if(vec[a[i]].size())add(1,vec[a[i]][vec[a[i]].size()-1]+1,i,0,1);
        int siz=vec[a[i]].size();
        for(int j=1;j<=k;j++){
            if(siz-j-1<0)break;
            // cout<<"del"<<vec[a[i]][siz-j-1]+1<<" "<<vec[a[i]][siz-j]<<" "<<j-1<<"\n";
            add(1,vec[a[i]][siz-j-1]+1,vec[a[i]][siz-j],j-1,-1);
        }
        vec[a[i]].push_back(i);siz++;
        for(int j=1;j<=k;j++){
            if(siz-j-1<0)break;
            // cout<<"add"<<vec[a[i]][siz-j-1]+1<<" "<<vec[a[i]][siz-j]<<" "<<j-1<<"\n";
            add(1,vec[a[i]][siz-j-1]+1,vec[a[i]][siz-j],j-1,1);
        }
        // cout<<v[1].sum[(1<<k)-1]<<"\n";
        ans+=v[1].sum[(1<<k)-1];
        // for(int i=1;i<=5;i++)cout<<i<<" "<<v[i].tag[0]<<" "<<v[i].sum[0]<<" "<<v[i].sum[1]<<'\n';
        //---****+++
    }
    cout<<ans<<"\n";
    return 0;
}